It is a common problem in computer systems to efficaciously manage the allocation of portions of a memory for storing segments of data. Data can include stored programs for manipulating the data. It is a particular problem to maximize the utilization of memory which can be used for storing such segments, at reasonable costs. The sizes of the allocable portions or "blocks" of memory are generally restrained by a predetermined allocation system. However, the sizes of the segments of data used or generated by programs can be unpredictably distributed over a widely varying range of sizes.
In designing an effective memory allocation system, one problem is to balance the efficiency of space utilization with the time required to allocated the space. Space utilization efficiencies are affected by memory fragmentation. Memory fragmentation makes otherwise free portions or blocks of memory unavailable for allocation. If the memory is highly fragmented, space is wasted. However, complex processes which minimize memory fragmentation consume time, and increase costs.
Memory fragmentation can be characterized as either internal or external fragmentation. Internal fragmentation is due to misfits between unpredictably sized segments of data and allocable blocks usually having predetermined sizes. If the incremental sizes difference between various allocable blocks is made large, a "good fit" with data segments is less likely, and the degree of internal fragmentation is high.
Conversely, if the incremental size differences between allocable blocks is made small, "checker-boarding" is observed resulting in a high degree of external fragmentation. That is, distributed throughout memory there are many small sized non-contiguous blocks which can only accommodate small segments of data, and are unavailable for larger segments of data.
Previous approaches to solve these problems have made trade-offs between space allocation efficiencies, e.g., reduced fragmentation, and the cost or time required to gain these efficiencies. For example, many versions of the "UNIX" operating system simply allocate memory blocks in sizes which are multiples of the powers of two. In other words, if the minimum allocable quantity is a byte, or a word (a word including a fixed number of bytes), the various sizes of the allocable blocks can be expressed as an integer power of two, e.g., 2.sup.i, where "i" is an integer. However, blocks can not be split or coalesced once created.
Although this type of allocation has a low processing cost, internal fragmentation tends to be high since many blocks might be almost twice as large as required. This is true because the ratio of the incremental differences between consecutively sized blocks is 2 to 1. That is, the blocks have relative sizes according to the progression of integer values 1, 2, 4, 8, 16, 32, and so forth. External fragmentation can also be high, since the pattern of allocable blocks can shift over time, and blocks previously created may be of the wrong size for current use.
Systems known as binary-buddy block systems have been developed to reduce external fragmentation inefficiencies. Binary-buddy block systems split blocks into a pair of equal sized allocable buddy blocks to accommodate smaller sized data segments. Subsequently, after use, the pair of buddy blocks can be coalesced to reform the original larger sized block, thereby reducing external fragmentation. However, the ratio of the incremental differences between consecutively sized blocks is still 2 to 1, thus the degree of internal fragmentation remains relatively high.
Internal fragmentation can be reduced by using Fibonacci numbers for proportioning block sizes. If the allocable memory blocks are sized according to the Fibonacci number series, the ratio between consecutively sized blocks can be reduced to approximately 1.6 to 1, thereby decreasing worst-case and average case internal fragmentation. However, with the Fibonacci system, the decrease in internal fragmentation is observed to be at a cost of a matching increase in external fragmentation.
Another system employed to minimize the ratio of consecutively sized blocks is a weighted-buddy block system. In the weighted-buddy block system the blocks are sized as multiples of either 2.sup.i, or 3(2.sup.i). The weighted-buddy block system decreases the worst-case incremental size difference ratio to approximately 1.5 to 1. However, not all allocable blocks in memory can be of a given size. In particular, at most three quarter of the allocable memory space can be used for requests for blocks of size 3(2.sup.i) for a given i, increasing external fragmentation. And, as for the Fibonacci system, the weighted-buddy block system reduces internal fragmentation at the expense of external fragmentation.
Taking the foregoing into consideration, it is apparent that there is a need for a memory allocation system which reduces the ratio between consecutively sized blocks in order to reduce internal fragmentation. Additionally, it is desirable that this smaller ratio be reached without increasing external fragmentation. Furthermore, the system should not increase the costs associated with allocating memory space. It is to these ends that the invention is directed.